package day20170407;

import org.junit.Test;

import utils.ArrayUtil;

public class QuickDemo {
	
	@Test
	public void quickTest() throws Exception {
		int[] arrays = {100,5,43,67,7,8,9,30};
		quick(arrays,0,arrays.length-1);
		
	}
	
	/**
	 * 快速排序法
	 * @param arrays	需要排序的数组
	 * @param begin		开始排序的下标
	 * @param end		结束排序的下标
	 */
	public void quick(int[] arrays,int begin,int end){
		
		//开始和结束的下标
		int i = begin;
		int j = end;
		
		ArrayUtil.arrayPrint(arrays);
		System.out.println("begin=" + begin + ",end=" + end);
		
		//判断i是否等于j，等于则结束这个方法，因为最后分离成一个
		if(begin >= end){
			System.out.println("结束方法，不用循环...");
			return;	
		}
		
		//拿到数组的第一个值
		int key = arrays[i];
		
		while(true){
			while(j > i){
				//有右到左扫描
				if(arrays[j] < key){
					//调用工具类互换位置
					ArrayUtil.dataPosition(arrays, i, j);
					break;
				}else{
					//如果没有则j--,继续从右到左扫描
					j--;
				}
			}
			
			while(j > i){
				//从左到右扫描
				if(arrays[i] > key){
					//调用工具类互换位置
					ArrayUtil.dataPosition(arrays, i, j);
					break;
				}else{
					//如果没有则i++,继续从左到右扫描
					i++;
				}
			}
			
			//如果i==j,则跳出外面的循环
			if(i == j){
				break;
			}
		}
		
		//递归
		//左边拆分出来的子数组
		quick(arrays, begin, i-1);
		
		//右边拆分出来的子数组
		quick(arrays, i+1, end);
		
		
	}
}
